The present invention relates generally to a processor-based technique in the field of computer graphics, and more particularly, to a technique for mapping line segment intersections to machine representable points such that the machine representable intersections are topologically consistent with and geometrically close to the original line segment intersections.
Many types of computer-implemented applications in the field of computer graphics model sets of intersecting line segments in a plane. Fundamental to the functions of interacting with and the visual display of objects modeled as sets of line segments is the problem of finding and correctly representing their intersections. This is a fundamental step for such problems as hidden surface elimination, set operations on polygons, and the decomposition of complex polygons into simpler components (such as triangles, trapezoids, or monotone regions.)
A set of line segments in a plane has certain geometric and topological properties as a result of the relationship among the line segments in the plane. The geometric properties include the positions of the line segments in the plane, typically specified by their endpoints, and the geometric definition of the edges; the topological information indicates the incidence and adjacency of the vertices and edges.
Algorithms that manipulate line segments may be characterized according to whether they are developed assuming an infinite precision or a finite precision model of computer arithmetic. With respect to such algorithms in general, it is customary to assume, unless specifically stated otherwise, that arithmetic operations are carried out with infinite precision, in what may be referred to as the continuous domain. The implementation of geometric algorithms on computer graphics systems, however, often must deal with the limited arithmetic precision of geometric computations. Rather than simply analyzing the errors introduced by the computer, it is often necessary to redesign the algorithms entirely, taking into account the finite resolution of the machine arithmetic, to handle potential errors such as degeneracies (e.g., coincident lines, or multiple lines sharing the same intersection.)
One potential result of errors produced when an algorithm developed using an infinite precision arithmetic model is implemented using finite precision arithmetic is that after manipulation the position of the intersections of the line segments may no longer be topologically consistent with their positions when they were originally received. For example, mapping an intersection of two line segments to a representable point may introduce additional intersections in the two line segments that are not actually present in the original spatial distribution of the lines. Repeated mapping of the location of an intersection of two line segments that results from finite precision computations could produce a final representation of the location of the intersection that is unacceptably distant from the actual location of the intersection of the original line segments, a problem that may be described as "drifting" of an output representable line segment. Depending on the nature and purpose for which the line segments are being used, these inconsistencies may have adverse real-world consequences to a user of an application that depends, for example, on accurately locating a point in a region formed by the intersecting line segments.
Algorithms manipulating line segments in the discrete domain have been suggested by Daniel H. Greene and Frances F. Yao, in "Finite-Resolution Computational Geometry," Proc. 27th Ann. Symp. on Foundations of Computer Science, 1986, pp. 143-152 (hereafter, "the Greene and Yao paper"). Greene and Yao disclose a technique for mapping the intersections in a set of line segments to machine representable points. Greene and Yao use a tiling of machine representable points, treating each representable point in a tile as an "obstacle," and do not allow segments to go over an obstacle while intersections move to their nearest machine representable point. The movement of the intersections causes additional line segments, called fragments, to be added to a line segment, and adhering to the obstacle rule results in adding more fragments to a line segment. Greene and Yao show that no topological inconsistencies arise between the original set of line segments and the fragmented line segments that result from using their technique. Greene and Yao disclose a three-pass algorithm for computing the machine representable intersections efficiently; this algorithm uses a discrete version of a well-known algorithm known as the plane sweep algorithm, in computing the machine representable intersections.
For many applications that handle significant numbers of line segments, the Greene-Yao mapping of intersections to representable points has the undesirable property of creating a large number of breaks in the original line segment in order to accommodate the requirement of not going over the obstacles. While these breaks produce line segments having machine representable intersections that are geometrically very close to the original line segments, they also produce very fragmented line segments, which has an adverse effect on the efficiency of algorithms and operations that use these fragmented line segments.